package com.sali.数据结构;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

 实现 MinStack 类:

 MinStack() 初始化堆栈对象。
 void push(int val) 将元素val推入堆栈。
 void pop() 删除堆栈顶部的元素。
 int top() 获取堆栈顶部的元素。
 int getMin() 获取堆栈中的最小元素。
 */
public class LeetCode_155 {

    Deque<Integer> minStack;
    Deque<Integer> dataStack;

    public LeetCode_155() {
        minStack = new ArrayDeque<>();
        dataStack = new ArrayDeque<>();
    }

    public void push(int val) {
        dataStack.push(val);
        if ( minStack.isEmpty() || minStack.peek() >= val ) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = dataStack.pop();
        if ( !minStack.isEmpty() && minStack.peek() == val ) {
            minStack.pop();
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

}
